﻿//class Solution
//{
//public:
//	int largestSumAfterKNegations(vector<int>& nums, int k)
//	{
//		int m = 0, minElem = INT_MAX, n = nums.size();
//		for (auto x : nums)
//		{
//			if (x < 0) m++;
//			minElem = min(minElem, abs(x)); 
//		}
//		int ret = 0;
//		if (m > k)
//		{
//			sort(nums.begin(), nums.end());
//			for (int i = 0; i < k; i++) 
//			{
//				ret += -nums[i];
//			}
//			for (int i = k; i < n; i++) 
//			{
//				ret += nums[i];
//			}
//		}
//		else
//		{
//			for (auto x : nums) ret += abs(x);
//			if ((k - m) % 2) 
//			{
//				ret -= minElem * 2;
//			}
//		}
//		return ret;
//	}
//};




//class Solution
//{
//public:
//	int monotoneIncreasingDigits(int n)
//	{
//		string s = to_string(n); 
//		int i = 0, m = s.size();
//		// 找第⼀个递减的位置
//		while (i + 1 < m && s[i] <= s[i + 1]) i++;
//		if (i + 1 == m) return n; 
//		// 回推
//		while (i - 1 >= 0 && s[i] == s[i - 1]) i--;
//		s[i]--;
//		for (int j = i + 1; j < m; j++) s[j] = '9';
//		return stoi(s);
//	}
//};



class Solution
{
	public int canCompleteCircuit(int[] gas, int[] cost)
	{
		int n = gas.length;
		for (int i = 0; i < n; i++) 
		{
			int rest = 0;
			int step = 0;
			for (; step < n; step++) 
			{
				int index = (i + step) % n;
				rest = rest + gas[index] - cost[index];
				if (rest < 0)
				{
					break;
				}
			}
			if (rest >= 0)
			{
				return i;
			}
			i = i + step; 
		}
		return -1;
	}
}